import javax.print.DocFlavor;
import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    Map<Integer,Integer> map=new HashMap<>();
    int max=Integer.MIN_VALUE;
    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        List<Integer> list=new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()==max){
                list.add(entry.getKey());
            }
        }
        int[] arr=new int[list.size()];
        for(int i=0;i<list.size();i++){
            arr[i]=list.get(i);
        }
        return arr;
    }
    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        int sumKey=left+right+root.val;
        int value=map.getOrDefault(sumKey,0)+1;
        map.put(sumKey,value);
        max=Math.max(value,max);
        return sumKey;
    }













    public String customSortString(String order, String s) {
        int[] arr=new int[26];
        for(int i=0;i<s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        StringBuilder sb=new StringBuilder();
        for(char ch : order.toCharArray()){
            for(int i=0;i<arr[ch-'a'];i++){
                sb.append(ch);
            }
            arr[ch-'a']=0;
        }
        for(char i='a';i<='z';i++){
            for(int j=0;j<arr[i-'a'];j++){
                sb.append(i);
            }
        }
        return sb.toString();
    }



















    public int countSubstrings(String s, String t) {
        int ret=0;
        for(int i=0;i<s.length();i++){
            for(int j=0;j<t.length();j++){
                if(s.charAt(i)!=t.charAt(j)){
                    int left=1;
                    int right=1;
                    while (i+right<s.length()&&j+right<t.length()&&s.charAt(i+right)==t.charAt(j+right)){
                        right++;
                    }
                    while (i-left>=0&&j-left>=0&&s.charAt(i-left)==t.charAt(j-left)){
                        left++;
                    }
                    ret+=left*right;
                }
            }
        }
        return ret;
    }




















    public List<String> getValidT9Words(String num, String[] words) {
        List<String> list=new ArrayList<>();
        Map<Character,Integer> map=new HashMap<>();
        map.put('a',2);
        map.put('b',2);
        map.put('c',2);
        map.put('d',3);
        map.put('e',3);
        map.put('f',3);
        map.put('g',4);
        map.put('h',4);
        map.put('i',4);
        map.put('j',5);
        map.put('k',5);
        map.put('l',5);
        map.put('m',6);
        map.put('n',6);
        map.put('o',6);
        map.put('p',7);
        map.put('q',7);
        map.put('r',7);
        map.put('s',7);
        map.put('t',8);
        map.put('u',8);
        map.put('v',8);
        map.put('w',9);
        map.put('x',9);
        map.put('y',9);
        map.put('g',9);
        for(String str : words){
            StringBuffer sb=new StringBuffer();
            for(char ch : str.toCharArray()){
                sb.append(map.get(ch));
            }
            String s= sb.toString();
            if(s.equals(num)){
                list.add(str);
            }
        }
        return list;
    }














    public int numSpecialEquivGroups(String[] words) {
        Set<String> set=new HashSet<>();
        for(String str : words){
            int[] arr=new int[52];
            for(int i=0;i<str.length();i++){
                arr[str.charAt(i)-'a'+26*(i%2)]++;
            }
            set.add(Arrays.toString(arr));
        }
        return set.size();
    }












    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list=new ArrayList<>();
        for(String s:words){
            if(method(s,pattern)) {
                list.add(s);
            }
        }
        return list;
    }
    public boolean method(String s,String p){
        Map<Character,Character> mapS=new HashMap<>();
        Map<Character,Character> mapP=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char chS=s.charAt(i);
            char chP=p.charAt(i);
            if(!mapS.containsKey(chS)){
                mapS.put(chS,chP);
            }
            if(!mapP.containsKey(chP)){
                mapP.put(chP,chS);
            }
            if(mapS.get(chS)!=chP||mapP.get(chP)!=chS){
                return false;
            }
        }
        return true;
    }





















    public int minSteps(String s, String t) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char chS=s.charAt(i);
            char chT=t.charAt(i);
            map.put(chS,map.getOrDefault(chS,0)+1);
            map.put(chT,map.getOrDefault(chT,0)-1);
        }
        int ret=0;
        for(Map.Entry<Character,Integer> entry : map.entrySet()){
            if(entry.getValue()>0){
                ret+=entry.getValue();
            }
        }
        return ret;
    }

















    String[] str={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    int[] arr={1000,900,500,400,100,90,50,40,10,9,5,4,1};
    public String intToRoman(int num) {
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<arr.length;i++){
            String s=str[i];
            int value=arr[i];
            while (num>=value){
                num-=value;
                sb.append(s);
            }
            if(num==0){
                break;
            }
        }
        return sb.toString();
    }
}








class OrderedStream {
    String[] str;
    int index=0;
    public OrderedStream(int n) {
        str=new String[n];
    }

    public List<String> insert(int idKey, String value) {
        List<String> list=new ArrayList<>();
        str[idKey-1]=value;
        for(int i=index;i<str.length;i++){
            if(str[index]==null){
                break;
            }else{
                list.add(str[i]);
                index++;
            }
        }
        return list;
    }
}

























class Codec {

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        return longUrl;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return shortUrl;
    }
}